package com.LeeCode;

import java.util.*;

/**
 * 组合总和 II
 */

public class Code040 {
    public static void main(String[] args) {
        int[] candidates = {2, 5, 2, 1, 2};
        int target = 8;
        System.out.println(new Code040().combinationSum2(candidates, target));

    }

    public List<List<Integer>> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates); // 先排序
        List<List<Integer>> result = new ArrayList<>();
        backtrace(candidates, result, new ArrayList<>(), target, 0);
        return result;
    }

    private void backtrace(int[] candidates, List<List<Integer>> result, List<Integer> current, int target, int start) {
        if (target == 0) {
            result.add(new ArrayList<>(current)); // 直接加入结果，无需去重
            return;
        }

        for (int i = start; i < candidates.length; i++) {
            // 第几层递归表示第几个位置，第i个位置上的元素不重复
            if (i > start && candidates[i] == candidates[i - 1]) {
                continue; // 跳过重复数字
            }
            if (target - candidates[i] < 0) {
                break; // 提前终止
            }
            current.add(candidates[i]);
            backtrace(candidates, result, current, target - candidates[i], i + 1); // 不能重复使用，所以 i + 1
            current.remove(current.size() - 1); // 回溯
        }
    }
}
